# 给定两个整数数组 preorder 和 inorder
# 其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
#
#  示例：
# 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
# 输出: [3,9,20,null,null,15,7]
from com.example.tree.tree_node import TreeNode
from typing import Optional, List


class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        inorder_map = {num: i for i, num in enumerate(inorder)}

        # 用 preorder[preorder:pre_right+1] 和 inorder[in_left:in_right+1],还原二叉树
        def build(pre_left: int, pre_right: int, in_left: int, in_right: int) -> \
                Optional[TreeNode]:
            if pre_left > pre_right:
                return None
            root = TreeNode(val=preorder[pre_left])
            root_in_inorder_index = inorder_map[root.val]  # root.val 在 inorder 中的位置
            left_children_size = root_in_inorder_index - 1 - in_left + 1
            # inorder[in_left:root_in_inorder_index] 是左子树的中序; inorder[root_in_inorder_index+1:in_right] 是右子树的中序
            # preorder[pre_left + 1:pre_left + left_children_size + 1] 是左子树的前序;
            # preorder[pre_left + left_children_size + 1+1:pre_right] 是右子树的前序
            root.left = build(pre_left + 1, pre_left + left_children_size, in_left, root_in_inorder_index - 1)
            root.right = build(pre_left + left_children_size + 1, pre_right, root_in_inorder_index + 1, in_right)
            return root

        return build(0, len(preorder) - 1, 0, len(inorder) - 1) if preorder and len(preorder) else None


if __name__ == "__main__":
    preorder, inorder = [3, 9, 20, 15, 7], [9, 3, 15, 20, 7]
    print(preorder[1:3])
    # Solution().buildTree(preorder, inorder)
